
/**
 * 
 * 书籍叠放
 * 
 * 题目描述

书籍的长、宽都是整数对应 (l,w)。如果书 A 的长宽度都比 B 长宽大时，则允许将 B 排列放在 A 上面。

现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个规格书籍能叠放在一起。

输入描述
输入：books = [[20,16],[15,11],[10,10],[9,10]]

说明：总共4本书籍，第一本长度为20宽度为16；第二本书长度为15宽度为11，依次类推，最后一本书长度为9宽度为10.

输出描述
输出：3

说明: 最多3个规格的书籍可以叠放到一起, 从下到上依次为: [20,16],[15,11],[10,10]

用例
输入	[[20,16],[15,11],[10,10],[9,10]]
输出	3
说明	最多3个规格的书籍可以叠放到一起, 从下到上依次为: [20,16],[15,11],[10,10]

 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 
 * 题目解析
本题的原型题是：LeetCode - 354 俄罗斯套娃信封问题_信封嵌套leetcode-CSDN博客

本题的书籍叠放条件是：书籍A的长 < 书籍B的长 且 书籍A的宽 < 书籍B的宽，此时书籍A才能叠放在书籍B上面。

首先，可以将所有书籍进行排序：

优先按照长度升序
如果长度相同，则按照宽度降序
这样排序的目的是为了忽略长度维度，仅考虑宽度维度。

排序后，前面书籍A的长度length 必然不大于 后面书籍B的长度length。
若 A.length < B.length，则此时只需要比较 A.width 和 B.width，若A.width < B.width的话，在A可以叠放在B上。
若 A.length == B.length，则此时A必然不能叠放在B上，由于A，B的长度相同时，会继续按照宽度降序，即A.width >= B.width，则从宽度维度看，A也不能叠放在B上。
比如：[[20,16],[15,11],[10,10],[9,10]]，排序后：[[9,10],[10,10],[15,11],[20,16]]

忽略长度维度后，只关注宽度维度数组的话为：[10,10,11,16]

此时，最大叠放书籍个数，即为宽度维度数组的最长递增子序列长度。

假设我们要求求解 nums 数组的最长递增子序列长度，那么我们可以定义一个 dp 数组，长度为 nums.length。

dp[i] 的含义是：以 nums[i] 结尾最长递增子序列的长度。
初始时，dp[i] = 1，即初始时以 nums[i] 结尾最长递增子序列就是 nums[i] 自身。
dp[i] 取决于 dp[0] ~ dp[i - 1]

若 nums[i] > nums[0]，则 dp[i] = dp[0] + 1
若 nums[i] > nums[1]，则 dp[i] = dp[1] + 1
....
若 nums[i] > nums[i-1]，则 dp[i] = dp[i-1] + 1
dp[i] 只要保留上面最大值即可。

 */
public class 书籍叠放 {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
 
        ArrayList<int[]> books = new ArrayList<>();
 
        Matcher matcher = Pattern.compile("(\\d+),(\\d+)").matcher(sc.nextLine());
        while (matcher.find()) {
            int l = Integer.parseInt(matcher.group(1));
            int w = Integer.parseInt(matcher.group(2));
            books.add(new int[]{l, w});
        }
 
        // 书籍优先按照长度升序，对于长度相同的书籍，则继续按照宽度降序
        books.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
 
        // 宽度数组
        int[] width = new int[books.size()];
        for (int i = 0; i < books.size(); i++) {
            width[i] = books.get(i)[1];
        }
 
        // 求宽度维度上的最长递增子序列
        System.out.println(lengthLIS(width));
    }
 
    public static int lengthLIS(int[] nums) {
        // dp[i] 表示 以nums[i]结尾的最长递增子序列长度
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
 
        int ans = dp[0];
 
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
 
            ans = Math.max(ans, dp[i]);
        }
 
        return ans;
    }

}
